package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bracket-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 括号_08_09 {

    /* 参考题目 ： 括号生成_22
    * 这题做过，但我记得的思路就是 获得所有的结果，然后判断是否正确
    * 另一个解法则是： 保证每次生成的序列都是正确的
    * 也就是说：只有当 左括号>右括号时，才可以添加右括号
    * 而且要保证 左括号 >=右括号
    * 左括号先于右括号添加
    * */
    private List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        f(new StringBuilder(),n,0,0);
        return result;
    }
    public void f(StringBuilder temp,int n,int left,int right){
        if(temp.length() == 2*n){
            // 括号生成完毕了
            result.add(new String(temp));
        }
        if(left < n ){
            // 说明还可以添加左括号
            temp.append('(');
            f(temp,n,left+1,right);
            // 回溯
            temp.deleteCharAt(temp.length()-1);
        }
        if(right < left){
            // 只有当 右括号的个数小于左括号时，才可以进行添加
            temp.append(')');
            f(temp,n,left,right+1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }


}
